BOJ_14002_가장 긴 증가하는 부분 수열4

LIS(Longest Increasing Subsequence) 알고리즘을 사용해서 가장 긴 증가하는 부분 수열의 원소를 출력하는 문제

BOJ_11053_가장 긴 증가하는 부분 수열
BOJ_12015_가장 긴 증가하는 부분 수열2
BOJ_12738_가장 긴 증가하는 부분 수열3
에서는 길이만 출력했다면, 이번에는 원소를 같이 출력해야 한다

N이 1000이기 때문에 dp만을 사용해서 풀어도 O(N^2) = O(1000^2)이기 때문에 시간적으로 괜찮다

package solve.BJO;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.*;  
  
public class BJO_14002_가장_긴_증가하는_부분_수열4 {  
    public static void main(String[] args) throws IOException {  
        // 4번 문제는 dp로 풀어도 되지만 연습 겸 dp + 이분탐색으로 풀었다  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int N = Integer.parseInt(br.readLine());  
  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        int[] nums = new int[N];  
        for (int i = 0; i < N; i++) {  
            nums[i] = Integer.parseInt(st.nextToken());  
        }  
  
        // dp 배열과 이분탐색을 함께 사용해서  
        // 수열의 정확한 원소를 구하는 문제  
        // 시간복잡도 : NlogN        int[] dp = new int[N];  
        int[] lis = new int[N];  
  
        int length = 0;  
        for (int i = 0; i < N; i++) {  
            int num = nums[i];  
            int pos = binarySearch(lis, 0, length, num);  
            lis[pos] = num;  
            dp[i] = pos;  
  
            if (pos == length) length++;  
        }  
  
        System.out.println(length);  
  
        Integer[] res = new Integer[length];  
        length--;  
        for (int i = N - 1; i >= 0; i--) {  
            if (dp[i] == length) {  
                res[length] = nums[i];  
                length--;  
            }  
        }  
  
        for (Integer num : res) {  
            System.out.print(num + " ");  
        }  
    }  
  
    public static int binarySearch(int[] lis, int start, int end, int target) {  
        while (start < end) {  
            int mid = start + (end - start) / 2;  
  
            if (lis[mid] < target) start = mid + 1;  
            else end = mid;  
        }  
  
        return start;  
    }  
}